package com.datastructure.test.judgeuglynumber;

import java.util.*;
import java.util.stream.Collectors;

public class JudgeUglyNumber {
    private Set<Integer> set = new HashSet<>();
    private int result =0;
    public static void main(String[] args) {
        JudgeUglyNumber judgeUglyNumber = new JudgeUglyNumber();
        int getUglyNumber_solution = judgeUglyNumber.GetUglyNumber_Solution(7);
        System.out.println(getUglyNumber_solution);
    }

    public int GetUglyNumber_Solution1(int index) {
        if(index<=0) return 0;
        int p2=0,p3=0,p5=0;
        int[] result=new int[index];
        result[0]=1;
        for(int i=1;i<index;i++){
            result[i]=Math.min(result[p2]*2,Math.min(result[p3]*3,result[p5]*5));
            if(result[i]==result[p2]*2) p2++;//之前的每一个丑数都需要进行乘以2或者3或者5的操作。p2,p3,p5用来记录当前那个丑数之前已经进行完乘2的操作了
            if(result[i]==result[p3]*3) p3++;
            if(result[i]==result[p5]*5) p5++;
        }
        return result[index-1];
    }

    public int GetUglyNumber_Solution(int index) {
        set.add(1);
        computeUgly(1,index);
        return result;
//        int i = 0;
//        do {
//            i++;
//            if(isUgly(i)){
//                stack.add(i);
//            }
//        } while (stack.size() != index);
//        return stack.pop();
    }

    private void computeUgly(int i,int index){
        set.add(i*2);
        set.add(i*3);
        set.add(i*5);
        if(set.size()>index){
            List<Integer> collect = new ArrayList<>(set).stream().sorted().collect(Collectors.toList());
            result=collect.get(index-1);
            return;
        }
        computeUgly(i*2,index);
        computeUgly(i*3,index);
        computeUgly(i*5,index);
    }

    private boolean isUgly(int i) {
        if(i==1){
            return true;
        }
        return dfs(i,2)
                ||dfs(i,3)
                ||dfs(i,5);
    }

    private boolean dfs(int dividend,int divide) {
        int trade = dividend/divide;
        int remainder = dividend%divide;
        if(remainder!=0){
            return false;
        }
        if(trade == 1){
            return true;
        }
        return dfs(trade,2)
                ||dfs(trade,3)
                ||dfs(trade,5);
    }
}
